package 力扣;

import java.util.LinkedList;
import java.util.List;

/**
 输入: 3
 输出: 5
 解释:
 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

 1         3     3      2      1
 \       /     /      / \      \
 3     2     1      1   3      2
 /     /       \                 \
 2     1         2                 3

 */
public class _96不同的二叉搜索树 {
    public class TreeNode {
        int val;
       TreeNode left;
       TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val,TreeNode left,TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int numTrees(int n) {
            if( n < 1 ) return 1;

        List<TreeNode> treeNodes = generateSubtrees(1, n);
        return treeNodes.size();
    }

    private List<TreeNode> generateSubtrees(int l, int r) {
        LinkedList<TreeNode> res = new LinkedList<TreeNode>();
        if( l > r){
            res.add(null);
            return res;
        }

        for (int i = l; i <= r; i++) {
            List<TreeNode> leftNodes = generateSubtrees(l,i-1);
            List<TreeNode> rightNodes = generateSubtrees(i+1,r);
            for (TreeNode leftNode: leftNodes){
                for (TreeNode rightNode :
                        rightNodes) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftNode;
                    root.right = rightNode;
                    res.add(root);
                }
            }
        }
        return res;
    }
}
